//Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal
//'s triangle. 
//
// In Pascal's triangle, each number is the sum of the two numbers directly abov
//e it as shown: 
//
// 
// Example 1: 
// Input: rowIndex = 3
//Output: [1,3,3,1]
// Example 2: 
// Input: rowIndex = 0
//Output: [1]
// Example 3: 
// Input: rowIndex = 1
//Output: [1,1]
// 
// 
// Constraints: 
//
// 
// 0 <= rowIndex <= 33 
// 
//
// 
// Follow up: Could you optimize your algorithm to use only O(rowIndex) extra sp
//ace? 
// Related Topics 数组 
// 👍 282 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：Pascal's Triangle II
class P119PascalsTriangleIi {
    public static void main(String[] args) {
        Solution solution = new P119PascalsTriangleIi().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> father = new ArrayList<>();
            for (int i = 0; i <= rowIndex; i++) {
                List<Integer> child = new ArrayList<>();
                if (father.isEmpty()) {
                    child.add(1);
                } else {
                    child.add(1);
                    for (int j = 1; j < father.size(); j++) {
                        child.add(father.get(j - 1) + father.get(j));
                    }
                    child.add(1);
                }
                father = child;

            }
            return father;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}